1. Field of the Invention
The present invention relates to communication networks and, more particularly, to a method and apparatus for source implemented constraint based routing with source routed protocol data units.
2. Description of the Related Art
Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as Internet Protocol packets, Ethernet Frames, data cells, segments, or other logical associations of bits/bytes of data, between the network elements by utilizing one or more communication links between the devices. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
There exists a class of networks in which traffic patterns are very focused. In particular, the traffic in these networks generally flows either from a well known focal point out to all the other nodes, or the reverse, from all those nodes back to the focal point. In these networks rarely, if ever, does traffic flow in any other pattern. One example of a network that generally exhibits these characteristics is a wireless ad-hoc network containing a network of wireless routers spanning a neighborhood and providing wireless access to individual users in the neighborhood, although the invention is not limited to an implementation in this particular type of network.
FIG. 1 illustrates a network in which a focal point F acts as an interface between a group of network elements interconnected in a mesh network configuration. The network elements may be wireless access devices or other types of network elements. Within the mesh, the network elements are typically homogenous devices having approximately equal capacity. For example, the network elements may be wireless routers configured to transmit wireless signals using a particular protocol. Since the protocol defines the transmission bandwidth available over a given link between adjacent nodes, the network elements in this instance are practically limited to the protocol definition regardless of their physical capabilities.
Because of the focal-point in the network, traffic will congest on links adjacent the focal point if a shortest path routing protocol is used, such as Open Shortest Path First (OSPF) or Routing Information Protocol (RIP). This is especially true when traffic patterns are not well balanced.
To overcome this problem, it is necessary to apply constraint based routing to allow full use of the network while minimizing congestion. Several protocols have been developed to do constraint based routing. For example, OSPF-Traffic Engineering (OSPF-TE) and MultiProtocol Label Switching-Traffic Engineering (MPLS-TE) both have been developed to determine constraint-based paths through the network and enable reservations to be made on the network. Specifically, with OSPF-TE and MPLS signaling, each node on the network maintains a table of links and constraints on the links. Thus, when a new connection is to be added to the network, the connection is signaled on the network and a new path is determined for the connection. Once the new path is determined, the path is signaled with PATH/RESV messages according to the MPLS protocol. Finally, OSPF-TE re-floods the new available bandwidth on the traversed links after admission control completes at each of the intermediate nodes on the path.
Unfortunately, any time a reservation is made or altered in OSPF-TE or one of the other traffic engineering protocols, a link state advertisement (LSA) must be broadcast on the network to enable other nodes on the network to update their topology map with the new reservation information. Flooding of LSAs is acceptable on a network having a small number of nodes and links, however it can become onerous where the network becomes quite large. Additionally, where the links are of limited bandwidth, such as in the wireless area, using a portion or potentially a relatively large portion of that bandwidth to communicate LSAs between the nodes is an undesirable proposition.